home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / zoo / lzd.c < prev    next >
C/C++ Source or Header  |  1980-01-02  |  28KB  |  850 lines
  1. #ifndef LINT
  2. static char sccsid[]="@(#) lzd.c 2.6 88/01/30 20:39:18";
  3. #endif /* LINT */
  4.  
  5. /*********************************************************************/
  6. /* This file contains two versions of the lzd() decompression routine.
  7. The default is to use a fast version coded by Ray Gardner.    If the
  8. symbol SLOW_LZD is defined, the older slower one is used.  I have tested
  9. Ray's code and it seems to be portable and reliable.  But if you
  10. suspect any problems you can define SLOW_LZD for your system in
  11. options.h and cause the older code to be used.    --R.D. */
  12. /*********************************************************************/
  13.  
  14. #include "options.h"
  15. #include "zoo.h"
  16. #include "zooio.h"
  17. #include "various.h"
  18. #include "zoofns.h"           /* function definitions */
  19. #include "zoomem.h"
  20. #include "debug.h"
  21. #include "assert.h"
  22. #include "lzconst.h"
  23.  
  24. #ifndef SLOW_LZD
  25.  
  26. /* Extensive modifications for speed by Ray Gardner
  27. ** Public domain by Raymond D. Gardner  9/26/88
  28. **
  29. ** I apologize for the comments being so dense in places as to impair
  30. ** readability, but some of the stuff isn't very obvious and needs
  31. ** some explaining.    I am also sorry for the messy control structure
  32. ** (quite a few labels and goto's) and very long lzd() function, but
  33. ** I don't know how to do this any other way without loss of speed.
  34. **
  35. ** Ray Gardner
  36. ** 6374 S. Monaco Ct.
  37. ** Englewood, CO 80111
  38. */
  39.  
  40. #ifdef ANSI_HDRS
  41. # include <string.h>     /* to get memcpy */
  42. #else
  43.   VOIDPTR memcpy();
  44. #endif
  45.  
  46. #define    STACKSIZE    4000    /* allows for about 8Mb string in worst case? */
  47. /* stack grows backwards in this version, using pointers, not counters */
  48. static char *stack;
  49. static char *stack_pointer;
  50. static char *stack_lim;
  51.  
  52. void init_dtab PARMS((void));
  53. unsigned rd_dcode PARMS((void));
  54. /* void wr_dchar (char); */      /* now a macro */
  55. void ad_dcode PARMS((void));
  56.  
  57. #ifdef FILTER
  58. /* to send data back to zoofilt */
  59. extern unsigned int filt_lzd_word;
  60. #endif /* FILTER */
  61.  
  62. void xwr_dchar PARMS ((int));
  63. static int firstchar PARMS ((int));
  64. static void cbfill PARMS ((void));
  65.  
  66. /* wr_dchar() is a macro for speed */
  67. #define wr_dchar(c) {                             \
  68.                                     if (outbufp<outbuflim) \
  69.                                         *outbufp++=(c);     \
  70.                                     else                          \
  71.                                         xwr_dchar(c);       \
  72.                           }
  73.  
  74. extern char *out_buf_adr;            /* output buffer */
  75. extern char *in_buf_adr;            /* input buffer */
  76.                              /* use pointers (not counters) for buffer (for speed) */
  77. static char *outbufp;                /* output buffer pointer */
  78. static char *outbuflim;             /* output buffer limit */
  79. static char *outbufguard;            /* output buffer "guard" */
  80.  
  81. char memflag = 0;                     /* memory allocated? flag */
  82. int *head;                                /* lzw prefix codes */
  83. char *tail;                             /* lzw suffix codes */
  84. static unsigned cur_code;
  85. static unsigned old_code;
  86. static unsigned in_code;
  87.  
  88. static unsigned free_code;
  89. static int nbits;
  90. static unsigned max_code;
  91.  
  92. /* We use a buffer of codes to avoid a function call to unpack each
  93. ** one as needed.  We allocate an extra slot past the end of the buffer
  94. ** and put a CLEAR code in it, to serve as a sentinel.  This way we can
  95. ** fold the test for code buffer runout into the test for a clear code
  96. ** and avoid having an extra test on each code processed.  Also, we don't
  97. ** always use the code buffer.  We can only use it when the input buffer
  98. ** is at a byte boundary, and when we know that the codesize won't change
  99. ** before we fill the code buffer, and when we know we won't run out of
  100. ** bytes in the input buffer before filling the code buffer.  So we start
  101. ** with the code buffer pointer pointing to the sentinel, and we always
  102. ** have it pointing at the sentinel when we can't (for one reason or
  103. ** another) be getting our codes from the code buffer.  We check for this
  104. ** condition whenever we get a CLEAR code, and if so, we get the code
  105. ** via the good old rd_dcode() routine.
  106. **
  107. ** One other problem with the code buffer approach is that we might get
  108. ** a CLEAR code in the middle of the buffer.  This means that the next
  109. ** code is only 9 bits, but we have probably already unpacked a number of
  110. ** larger codes from the input into the buffer before we discover this.
  111. ** So we remember where (in the input buffer) the code buffer was filled
  112. ** from, and when a CLEAR code is encountered in the buffer (not the
  113. ** sentinel at the end) we back up the bit_offset pointer in the input
  114. ** buffer, and reset things to start unpacking the 9-bit codes from there.
  115. */
  116.  
  117. #define CODEBUF_SIZE 64       /* must be multiple of 8, experiment for best */
  118. static unsigned codebuf[CODEBUF_SIZE+1];        /* code buffer */
  119. static unsigned *codebufp;         /* code buffer pointer */
  120. static unsigned *codebuflim;        /* code buffer limit */
  121.         /* bit offset within the input buffer of where the code buffer began */
  122. static unsigned codebufoffset;
  123.  
  124. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  125.                                 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  126. static unsigned bit_offset;    /* note this only allows max 8K input buffer!!*/
  127.  
  128. #ifdef UNBUF_IO
  129. #define        BLOCKFILE        int
  130. #define        BLOCKREAD        read
  131. #define        BLOCKWRITE        blockwrite
  132. int read PARMS ((int, VOIDPTR, unsigned));
  133. int write PARMS ((int, VOIDPTR, unsigned));
  134. int blockwrite PARMS ((int, VOIDPTR, unsigned));
  135. #else
  136. #define        BLOCKFILE        ZOOFILE
  137. #define        BLOCKREAD        zooread
  138. #define        BLOCKWRITE        zoowrite
  139. #endif /* UNBUF_IO */
  140.  
  141. static BLOCKFILE in_f, out_f;
  142.  
  143. /* rd_dcode() reads a code from the input (compressed) file and returns
  144. its value. */
  145. unsigned rd_dcode()
  146. {
  147.     register char *ptra, *ptrb;     /* miscellaneous pointers */
  148.     unsigned word;                           /* first 16 bits in buffer */
  149.     unsigned byte_offset;
  150.     char nextch;                                    /* next 8 bits in buffer */
  151.     unsigned ofs_inbyte;                   /* offset within byte */
  152.  
  153.     ofs_inbyte = bit_offset % 8;
  154.     byte_offset = bit_offset / 8;
  155.     bit_offset = bit_offset + nbits;
  156.  
  157.     assert(nbits >= 9 && nbits <= 13);
  158.  
  159.     if (byte_offset >= INBUFSIZ - 5) {
  160.         int space_left;
  161.  
  162.         assert(byte_offset >= INBUFSIZ - 5);
  163.         debug((printf ("lzd: byte_offset near end of buffer\n")))
  164.  
  165.         bit_offset = ofs_inbyte + nbits;
  166.         space_left = INBUFSIZ - byte_offset;
  167.         ptrb = byte_offset + in_buf_adr;             /* point to char */
  168.         ptra = in_buf_adr;
  169.         /* we now move the remaining characters down buffer beginning */
  170.         debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  171.         while (space_left > 0) {
  172.             *ptra++ = *ptrb++;
  173.             space_left--;
  174.         }
  175.         assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  176.         assert(space_left == 0);
  177.         if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  178.             prterror ('f', "I/O error in lzd:rd_dcode.\n");
  179.         byte_offset = 0;
  180.     }
  181.     ptra = byte_offset + in_buf_adr;
  182.  /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  183.     word = (unsigned char) *ptra; ptra++;
  184.     word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  185.  
  186.     nextch = *ptra;
  187.     if (ofs_inbyte != 0) {
  188.         /* shift nextch right by ofs_inbyte bits */
  189.         /* and shift those bits right into word; */
  190.         word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  191.     }
  192.     return (word & masks[nbits]);
  193. } /* rd_dcode() */
  194.  
  195. void init_dtab()
  196. {
  197.     nbits = 9;
  198.     max_code = 512;
  199.     free_code = FIRST_FREE;
  200. }
  201.  
  202. /* By making wr_dchar() a macro and calling this routine only on buffer
  203. ** full condition, we save a lot of function call overhead.
  204. ** We also use pointers instead of counters for efficiency (in the macro).
  205. */
  206. void xwr_dchar (ch)
  207. int ch;
  208. {
  209.     if (outbufp >= outbuflim) {      /* if buffer full */
  210.         if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
  211.                                                                 != outbufp - out_buf_adr)
  212.             prterror ('f', "Write error in lzd:wr_dchar.\n");
  213.         addbfcrc(out_buf_adr, outbufp - out_buf_adr);     /* update CRC */
  214.         outbufp = out_buf_adr;                         /* restore empty buffer */
  215.     }
  216.     assert(outbufp - out_buf_adr < OUTBUFSIZ);
  217.     *outbufp++ = ch;
  218. } /* wr_dchar() */
  219.  
  220.  
  221. /* Code buffer fill routines
  222. **
  223. ** We use a separate function for each code size.
  224. ** Each function unpacks 8 codes from a packed buffer (f)
  225. ** to an unpacked buffer (t)
  226. ** A lot of code space, but really speeds up bit picking.
  227. */
  228. static unsigned char f[13];    /* must be unsigned for right shifts */
  229. static unsigned t[8];
  230.  
  231. static void cb9fill ()
  232. {
  233.     t[0] = (f[0]     ) | ((f[1] &   1) << 8);
  234.     t[1] = (f[1] >> 1) | ((f[2] &   3) << 7);
  235.     t[2] = (f[2] >> 2) | ((f[3] &   7) << 6);
  236.     t[3] = (f[3] >> 3) | ((f[4] &  15) << 5);
  237.     t[4] = (f[4] >> 4) | ((f[5] &  31) << 4);
  238.     t[5] = (f[5] >> 5) | ((f[6] &  63) << 3);
  239.     t[6] = (f[6] >> 6) | ((f[7] & 127) << 2);
  240.     t[7] = (f[7] >> 7) | ((f[8]      ) << 1);
  241. }
  242.  
  243. static void cb10fill ()
  244. {
  245.     t[0] = (f[0]     ) | ((f[1] &   3) << 8);
  246.     t[1] = (f[1] >> 2) | ((f[2] &  15) << 6);
  247.     t[2] = (f[2] >> 4) | ((f[3] &  63) << 4);
  248.     t[3] = (f[3] >> 6) | ((f[4]      ) << 2);
  249.     t[4] = (f[5]     ) | ((f[6] &   3) << 8);
  250.     t[5] = (f[6] >> 2) | ((f[7] &  15) << 6);
  251.     t[6] = (f[7] >> 4) | ((f[8] &  63) << 4);
  252.     t[7] = (f[8] >> 6) | ((f[9]      ) << 2);
  253. }
  254.  
  255. static void cb11fill ()
  256. {
  257.     t[0] = (f[0]     ) | ((f[1] &   7) << 8);
  258.     t[1] = (f[1] >> 3) | ((f[2] &  63) << 5);
  259.     t[2] = (f[2] >> 6) | (f[3] << 2) | ((f[4] &  1) << 10);
  260.     t[3] = (f[4] >> 1) | ((f[5] &  15) << 7);
  261.     t[4] = (f[5] >> 4) | ((f[6] & 127) << 4);
  262.     t[5] = (f[6] >> 7) | (f[7] << 1) | ((f[8] &  3) <<  9);
  263.     t[6] = (f[8] >> 2) | ((f[9] &  31) << 6);
  264.     t[7] = (f[9] >> 5) | ((f[10]     ) << 3);
  265. }
  266.  
  267. static void cb12fill ()
  268. {
  269.     t[0] = (f[0]     )  | ((f[1] & 15) << 8);
  270.     t[1] = (f[1] >> 4)  | ((f[2]     ) << 4);
  271.     t[2] = (f[3]     )  | ((f[4] & 15) << 8);
  272.     t[3] = (f[4] >> 4)  | ((f[5]     ) << 4);
  273.     t[4] = (f[6]     )  | ((f[7] & 15) << 8);
  274.     t[5] = (f[7] >> 4)  | ((f[8]     ) << 4);
  275.     t[6] = (f[9]     )  | ((f[10] & 15) << 8);
  276.     t[7] = (f[10] >> 4) | ((f[11]     ) << 4);
  277. }
  278.  
  279. static void cb13fill ()
  280. {
  281.     t[0] = (f[0] ) | ((f[1] & 31) << 8);
  282.     t[1] = (f[1] >> 5) | (f[2] << 3) | ((f[3] & 3) << 11);
  283.     t[2] = (f[3] >> 2) | ((f[4] & 127) << 6);
  284.     t[3] = (f[4] >> 7) | (f[5] << 1) | ((f[6] & 15) << 9);
  285.     t[4] = (f[6] >> 4) | (f[7] << 4) | ((f[8] & 1) << 12);
  286.     t[5] = (f[8] >> 1) | ((f[9] & 63) << 7);
  287.     t[6] = (f[9] >> 6) | (f[10] << 2) | ((f[11] & 7) << 10);
  288.     t[7] = (f[11] >> 3) | (f[12] << 5);
  289. }
  290.  
  291. /* vector of code buffer fill routines
  292. */
  293. void (*cbfillvec[])  PARMS ((void)) = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  294.             cb9fill, cb10fill, cb11fill, cb12fill, cb13fill };
  295.  
  296. /* cbfill -- main code buffer fill routine
  297. **
  298. ** moves data from inbuf[] to f[]
  299. ** then calls via vector to unpack to t[]
  300. ** then moves from t[] to codebuf[]
  301. ** A lot of moving around, but still faster than a lot of shifting and
  302. ** masking via variables (at least on a micro -- don't know about VAXen)
  303. **  Uses memcpy() for block move
  304. */
  305.  
  306. static void cbfill ()
  307. {
  308.     char *inbp;
  309.     inbp = in_buf_adr + bit_offset / 8;
  310.     codebufp = codebuf;
  311.     while ( codebufp < codebuflim ) {
  312.       memcpy((VOIDPTR) f, inbp, nbits);
  313.         (*cbfillvec[nbits])();
  314.         memcpy((VOIDPTR) codebufp, (VOIDPTR) t, 8 * sizeof(unsigned int));
  315.         inbp += nbits;
  316.         codebufp += 8;
  317.     }
  318.     bit_offset += nbits * CODEBUF_SIZE;
  319. }
  320.  
  321. /* The following is used in the KwKwK case because it's a pretty rare
  322. ** case, and doing it this way avoids the overhead of remembering the
  323. ** "finchar" (first input character) of every string
  324. */
  325. static int firstchar(code)    /* find first character of a code */
  326. int code;
  327. {
  328.     while ( code > 255 )
  329.         code = head[code];
  330.     return code;
  331. }
  332.  
  333. int lzd(input_f, output_f)
  334. BLOCKFILE input_f, output_f;              /* input & output files */
  335. {
  336.     in_f = input_f;                      /* make it avail to other fns */
  337.     out_f = output_f;                   /* ditto */
  338.     nbits = 9;
  339.     max_code = 512;
  340.     free_code = FIRST_FREE;
  341.     bit_offset = 0;
  342.     outbuflim = out_buf_adr + OUTBUFSIZ;    /* setup out buffer limit */
  343.     outbufguard = outbuflim - 12;      /* for checking avail. room in outbuf */
  344.         /* note must allow for as many characters as we special-case (8) */
  345.         /* used 12 for extra fudge factor (Rahul does it, so I can too) */
  346.     outbufp = out_buf_adr;                        /* setup output buffer ptr */
  347.     codebufp = codebuflim = &codebuf[CODEBUF_SIZE]; /* code buf ptr & limit */
  348.     *codebuflim = CLEAR; /* phony CLEAR sentinel past end of code buffer */
  349.  
  350.     if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1) /* fill input buffer */
  351.         return(IOERR);
  352.     if (memflag == 0) {
  353.       head = (int *) ealloc((MAXMAX+10) * sizeof(int));
  354.       tail = (char *) ealloc((MAXMAX+10) * sizeof(char));
  355.       stack = (char *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
  356.       memflag++;
  357.     }
  358.  
  359.     stack_pointer = stack_lim = stack + STACKSIZE; /* setup stack ptr, limit*/
  360.     init_dtab();             /* initialize table */
  361.  
  362. loop:
  363.     cur_code = *codebufp++; /* get code from code buffer */
  364.  
  365. goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
  366.     if (cur_code == Z_EOF) {
  367.         debug((printf ("lzd: Z_EOF\n")))
  368.  
  369.         if (outbufp != out_buf_adr) {
  370.             if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
  371.                                                                   != outbufp - out_buf_adr)
  372.                 prterror ('f', "Output error in lzd().\n");
  373.             addbfcrc(out_buf_adr, outbufp - out_buf_adr);
  374.  
  375.         }
  376. #ifdef FILTER
  377.         /* get next two bytes and put them where zoofilt can find them */
  378.         /* nbits known to be in range 9..13 */
  379.         bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
  380.         filt_lzd_word = rd_dcode();
  381.         filt_lzd_word |= (rd_dcode() << nbits);
  382.         filt_lzd_word &= 0xffff;
  383. #endif
  384.         return (0);
  385.     }
  386.  
  387.     assert(nbits >= 9 && nbits <= 13);
  388.  
  389.     if (cur_code == CLEAR) {          /* was it sentinel or real CLEAR ? */
  390.         if ( codebufp > codebuflim ) { /* it was the sentinel             */
  391.             if ( bit_offset % 8 == 0 && /* if we're on byte boundary and   */
  392.                          /* codesize won't change before codebuf is filled and */
  393.                          /* codebuf can be filled without running out of inbuf */
  394.                      free_code + CODEBUF_SIZE < max_code &&
  395.                      bit_offset / 8 + (CODEBUF_SIZE * 13 / 8) < INBUFSIZ - 10 ) {
  396.                 codebufoffset = bit_offset; /* remember where we were when */
  397.                 cbfill();             /* we filled the code buffer */
  398.                 codebufp = codebuf;     /* setup code buffer pointer */
  399.                 goto loop;                 /* now go get codes from code buffer */
  400.             }                        /* otherwise, use rd_dcode to get code */
  401.             codebufp = codebuflim;     /* reset codebuf ptr to sentinel */
  402.             cur_code = rd_dcode();   /* get code via rd_dcode() */
  403.             if ( cur_code != CLEAR ) /* if it's not CLEAR */
  404.                 goto got_code;          /* then go handle it */
  405.         } else {             /* else it's really a CLEAR code, not sentinel */
  406.  /* reset bit_offset to get next code in input buf after CLEAR code */
  407.             bit_offset = codebufoffset + (codebufp - codebuf) * nbits;
  408.         }
  409.         codebufp = codebuflim;         /* set code buf ptr to sentinel */
  410.         debug((printf ("lzd: CLEAR\n")))
  411.         init_dtab();                /* init decompression table, etc. */
  412.         old_code = cur_code = rd_dcode(); /* get next code after CLEAR */
  413.         if (cur_code == Z_EOF)     /* special case for 0-length files */
  414.             goto goteof;
  415.         wr_dchar(cur_code);         /* write it out */
  416.         goto loop;                         /* and get next code */
  417.     }
  418.  
  419. got_code: /* we got a code and it's not a CLEAR */
  420.  
  421.     if (cur_code == Z_EOF) {
  422.         debug((printf ("lzd: Z_EOF\n")))
  423.         if (outbufp != out_buf_adr) {
  424.             if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
  425.                                                                   != outbufp - out_buf_adr)
  426.                 prterror ('f', "Output error in lzd().\n");
  427.             addbfcrc(out_buf_adr, outbufp - out_buf_adr);
  428.         }
  429.         return (0);
  430.     }
  431.  
  432.     in_code = cur_code;                    /* save original code */
  433.     if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  434.         cur_code = old_code;                 /* previous code becomes current */
  435.                                                     /* push first character of old code */
  436.         *--stack_pointer = firstchar(old_code);
  437.         goto unwind;                            /* and go "unwind" the current code */
  438.     }                    /* (use general unwind because the stack isn't empty now) */
  439.  
  440. /* Unwind a code.  The basic idea is to use a sort of loop-unrolling
  441. ** approach to really speed up the processing by treating the codes
  442. ** which represent short strings (the vast majority of codes) as
  443. ** special cases.  Avoid a lot of stack overflow checking safely.
  444. */
  445.  
  446.     if (cur_code > 255) {                  /* if cur_code is not atomic */
  447.         *--stack_pointer = tail[cur_code];    /* push its tail code */
  448.         cur_code = head[cur_code];             /* and replace with its head code */
  449.     } else {                               /* else 1-byte string */
  450.         if ( outbufp > outbufguard ) /* if outbuf near end, */
  451.             goto write_stack;           /* write via general routine */
  452.         *outbufp++ = cur_code;          /* we got space, put char out */
  453.         goto add_code;                   /* add code to table */
  454.     }
  455.  
  456.     if (cur_code > 255) {                  /* if cur_code is not atomic */
  457.         *--stack_pointer = tail[cur_code];    /* push its tail code */
  458.         cur_code = head[cur_code];             /* and replace with its head code */
  459.     } else {                               /* else 2-byte string */
  460.         if ( outbufp > outbufguard ) /* if outbuf near end, */
  461.             goto write_stack;           /* write via general routine */
  462.         *outbufp++ = cur_code;          /* we got space, put char out, and */
  463.         goto move_1_char;               /* go move rest of stack to outbuf */
  464.     }
  465.     if (cur_code > 255) {                  /* if cur_code is not atomic */
  466.         *--stack_pointer = tail[cur_code];    /* push its tail code */
  467.         cur_code = head[cur_code];             /* and replace with its head code */
  468.     } else {                               /* else 3-byte string */
  469.         if ( outbufp > outbufguard ) /* if outbuf near end, */
  470.             goto write_stack;           /* write via general routine */
  471.         *outbufp++ = cur_code;          /* we got space, put char out, and */
  472.         goto move_2_char;               /* go move rest of stack to outbuf */
  473.     }
  474.  
  475. /* we handle codes representing strings of 4 thru 8 bytes similarly */
  476.  
  477.     if (cur_code > 255) {
  478.         *--stack_pointer = tail[cur_code];
  479.         cur_code = head[cur_code];
  480.     } else {                               /* 4-byte string */
  481.         if ( outbufp > outbufguard )
  482.             goto write_stack;
  483.         *outbufp++ = cur_code;
  484.         goto move_3_char;
  485.     }
  486.     if (cur_code > 255) {
  487.         *--stack_pointer = tail[cur_code];
  488.         cur_code = head[cur_code];
  489.     } else {                               /* 5-byte string */
  490.         if ( outbufp > outbufguard )
  491.             goto write_stack;
  492.         *outbufp++ = cur_code;
  493.         goto move_4_char;
  494.     }
  495.     if (cur_code > 255) {
  496.         *--stack_pointer = tail[cur_code];
  497.         cur_code = head[cur_code];
  498.     } else {                               /* 6-byte string */
  499.         if ( outbufp > outbufguard )
  500.             goto write_stack;
  501.         *outbufp++ = cur_code;
  502.         goto move_5_char;
  503.     }
  504.     if (cur_code > 255) {
  505.         *--stack_pointer = tail[cur_code];
  506.         cur_code = head[cur_code];
  507.     } else {                               /* 7-byte string */
  508.         if ( outbufp > outbufguard )
  509.             goto write_stack;
  510.         *outbufp++ = cur_code;
  511.         goto move_6_char;
  512.     }
  513.     if (cur_code > 255) {
  514.         *--stack_pointer = tail[cur_code];
  515.         cur_code = head[cur_code];
  516.     } else {                               /* 8-byte string */
  517.         if ( outbufp > outbufguard )
  518.             goto write_stack;
  519.         *outbufp++ = cur_code;
  520.         goto move_7_char;
  521.     }
  522.  
  523. /* Here for KwKwK case and strings longer than 8 bytes */
  524. /* Note we have to check stack here, but not elsewhere */
  525.  
  526. unwind:
  527.     while (cur_code > 255) {               /* if code, not character */
  528.         *--stack_pointer = tail[cur_code];             /* push suffix char */
  529.         if (stack_pointer < stack+12)
  530.             prterror ('f', "Stack overflow in lzd().\n");
  531.         cur_code = head[cur_code];             /* head of code is new code */
  532.     }
  533.  
  534. /* General routine to write stack with check for output buffer full */
  535.  
  536. write_stack:
  537.     assert(nbits >= 9 && nbits <= 13);
  538.     wr_dchar(cur_code);    /* write this code, don't need to stack it first */
  539.     while ( stack_pointer < stack_lim ) {
  540.         /* wr_dchar(*stack_pointer++); AArgh!!! */
  541.         wr_dchar(*stack_pointer);
  542.         stack_pointer++;
  543.     }
  544.     goto add_code;                                   /* now go add code to table */
  545.  
  546. /* Here to move strings from stack to output buffer */
  547. /* only if we know we have enough room in output buffer */
  548. /* because (outbufp <= outbufguard) */
  549.  
  550. move_7_char:
  551.     *outbufp++ = *stack_pointer++;
  552. move_6_char:
  553.     *outbufp++ = *stack_pointer++;
  554. move_5_char:
  555.     *outbufp++ = *stack_pointer++;
  556. move_4_char:
  557.     *outbufp++ = *stack_pointer++;
  558. move_3_char:
  559.     *outbufp++ = *stack_pointer++;
  560. move_2_char:
  561.     *outbufp++ = *stack_pointer++;
  562. move_1_char:
  563.     *outbufp++ = *stack_pointer++;
  564.  
  565. assert(stack_pointer == stack_lim); /* I haven't tested this! rdg */
  566.  
  567. /* add_code is now inline to avoid overhead of function call on */
  568. /*   each code processed */
  569.  
  570. add_code:
  571.     assert(nbits >= 9 && nbits <= 13);
  572.     assert(free_code <= MAXMAX+1);
  573.     tail[free_code] = cur_code;                     /* save suffix char */
  574.     head[free_code] = old_code;                     /* save prefix code */
  575.     free_code++;
  576.     assert(nbits >= 9 && nbits <= 13);
  577.     if (free_code >= max_code) {
  578.         if (nbits < MAXBITS) {
  579.             debug((printf("lzd: nbits was %d\n", nbits)))
  580.             nbits++;
  581.             assert(nbits >= 9 && nbits <= 13);
  582.             debug((printf("lzd: nbits now %d\n", nbits)))
  583.             max_code = max_code << 1;            /* double max_code */
  584.             debug((printf("lzd: max_code now %d\n", max_code)))
  585.         }
  586.     }
  587.     old_code = in_code;
  588.  
  589.     assert(nbits >= 9 && nbits <= 13);
  590.  
  591.     goto loop;
  592. } /* lzd() */
  593.  
  594. #else /* SLOW_LZD defined, so use following instead */
  595.  
  596. /*********************************************************************/
  597. /* Original slower lzd().                                            */
  598. /*********************************************************************/
  599.  
  600. /*
  601. Lempel-Ziv decompression.    Mostly based on Tom Pfau's assembly language
  602. code.  The contents of this file are hereby released to the public domain.
  603.                                             -- Rahul Dhesi 1986/11/14
  604. */
  605.  
  606. #define    STACKSIZE    4000
  607.  
  608. struct tabentry {
  609.     unsigned next;
  610.     char z_ch;
  611. };
  612.  
  613. void init_dtab PARMS((void));
  614. unsigned rd_dcode PARMS((void));
  615. void wr_dchar PARMS((int));
  616. void ad_dcode PARMS((void));
  617.  
  618. #ifdef FILTER
  619. /* to send data back to zoofilt */
  620. extern unsigned int filt_lzd_word;
  621. #endif /* FILTER */
  622.  
  623.  
  624. static unsigned stack_pointer = 0;
  625. static unsigned *stack;
  626.  
  627. #define    push(x)  {  \
  628.                             stack[stack_pointer++] = (x);                   \
  629.                             if (stack_pointer >= STACKSIZE)                 \
  630.                                 prterror ('f', "Stack overflow in lzd().\n");\
  631.                         }
  632. #define    pop()    (stack[--stack_pointer])
  633.  
  634. extern char *out_buf_adr;            /* output buffer */
  635. extern char *in_buf_adr;            /* input buffer */
  636.  
  637. char memflag = 0;                     /* memory allocated? flag */
  638. extern struct tabentry *table;    /* hash table from lzc.c */
  639. static unsigned cur_code;
  640. static unsigned old_code;
  641. static unsigned in_code;
  642.  
  643. static unsigned free_code;
  644. static int nbits;
  645. static unsigned max_code;
  646.  
  647. static char fin_char;
  648. static char k;
  649. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  650.                                 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  651. static unsigned bit_offset;
  652. static unsigned output_offset;
  653.  
  654. #ifdef UNBUF_IO
  655. #define        BLOCKFILE        int
  656. #define        BLOCKREAD        read
  657. #define        BLOCKWRITE        blockwrite
  658. int read PARMS ((int, VOIDPTR, unsigned));
  659. int write PARMS ((int, VOIDPTR, unsigned));
  660. #else
  661. #define        BLOCKFILE        ZOOFILE
  662. #define        BLOCKREAD        zooread
  663. #define        BLOCKWRITE        zoowrite
  664. #endif /* UNBUF_IO */
  665.  
  666. static BLOCKFILE in_f, out_f;
  667.  
  668. int lzd(input_f, output_f)
  669. BLOCKFILE input_f, output_f;              /* input & output file handles */
  670. {
  671.     in_f = input_f;                      /* make it avail to other fns */
  672.     out_f = output_f;                   /* ditto */
  673.     nbits = 9;
  674.     max_code = 512;
  675.     free_code = FIRST_FREE;
  676.     stack_pointer = 0;
  677.     bit_offset = 0;
  678.     output_offset = 0;
  679.  
  680.     if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1)
  681.         return(IOERR);
  682.     if (memflag == 0) {
  683.       table = (struct tabentry *) ealloc((MAXMAX+10) * sizeof(struct tabentry));
  684.       stack = (unsigned *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
  685.       memflag++;
  686.     }
  687.  
  688.     init_dtab();             /* initialize table */
  689.  
  690. loop:
  691.     cur_code = rd_dcode();
  692. goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
  693.     if (cur_code == Z_EOF) {
  694.         debug((printf ("lzd: Z_EOF\n")))
  695.         if (output_offset != 0) {
  696.             if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
  697.                 prterror ('f', "Output error in lzd().\n");
  698.             addbfcrc(out_buf_adr, output_offset);
  699.         }
  700. #ifdef FILTER
  701.         /* get next two bytes and put them where zoofilt can find them */
  702.         /* nbits known to be in range 9..13 */
  703.         bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
  704.         filt_lzd_word = rd_dcode();
  705.         filt_lzd_word |= (rd_dcode() << nbits);
  706.         filt_lzd_word &= 0xffff;
  707. #endif
  708.         return (0);
  709.     }
  710.  
  711.     assert(nbits >= 9 && nbits <= 13);
  712.  
  713.     if (cur_code == CLEAR) {
  714.         debug((printf ("lzd: CLEAR\n")))
  715.         init_dtab();
  716.         fin_char = k = old_code = cur_code = rd_dcode();
  717.         if (cur_code == Z_EOF)     /* special case for 0-length files */
  718.             goto goteof;
  719.         wr_dchar(k);
  720.         goto loop;
  721.     }
  722.  
  723.     in_code = cur_code;
  724.     if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  725.         cur_code = old_code;                 /* previous code becomes current */
  726.         push(fin_char);
  727.     }
  728.  
  729.     while (cur_code > 255) {               /* if code, not character */
  730.         push(table[cur_code].z_ch);         /* push suffix char */
  731.         cur_code = table[cur_code].next;     /* <w> := <w>.code */
  732.     }
  733.  
  734.     assert(nbits >= 9 && nbits <= 13);
  735.  
  736.     k = fin_char = cur_code;
  737.     push(k);
  738.     while (stack_pointer != 0) {
  739.         wr_dchar(pop());
  740.     }
  741.     assert(nbits >= 9 && nbits <= 13);
  742.     ad_dcode();
  743.     old_code = in_code;
  744.  
  745.     assert(nbits >= 9 && nbits <= 13);
  746.  
  747.     goto loop;
  748. } /* lzd() */
  749.  
  750. /* rd_dcode() reads a code from the input (compressed) file and returns
  751. its value. */
  752. unsigned rd_dcode()
  753. {
  754.     register char *ptra, *ptrb;     /* miscellaneous pointers */
  755.     unsigned word;                           /* first 16 bits in buffer */
  756.     unsigned byte_offset;
  757.     char nextch;                                    /* next 8 bits in buffer */
  758.     unsigned ofs_inbyte;                   /* offset within byte */
  759.  
  760.     ofs_inbyte = bit_offset % 8;
  761.     byte_offset = bit_offset / 8;
  762.     bit_offset = bit_offset + nbits;
  763.  
  764.     assert(nbits >= 9 && nbits <= 13);
  765.  
  766.     if (byte_offset >= INBUFSIZ - 5) {
  767.         int space_left;
  768.  
  769. #ifdef CHECK_BREAK
  770.     check_break();
  771. #endif
  772.  
  773.         assert(byte_offset >= INBUFSIZ - 5);
  774.         debug((printf ("lzd: byte_offset near end of buffer\n")))
  775.  
  776.         bit_offset = ofs_inbyte + nbits;
  777.         space_left = INBUFSIZ - byte_offset;
  778.         ptrb = byte_offset + in_buf_adr;             /* point to char */
  779.         ptra = in_buf_adr;
  780.         /* we now move the remaining characters down buffer beginning */
  781.         debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  782.         while (space_left > 0) {
  783.             *ptra++ = *ptrb++;
  784.             space_left--;
  785.         }
  786.         assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  787.         assert(space_left == 0);
  788.         if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  789.             prterror ('f', "I/O error in lzd:rd_dcode.\n");
  790.         byte_offset = 0;
  791.     }
  792.     ptra = byte_offset + in_buf_adr;
  793.     /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  794.     word = (unsigned char) *ptra; ptra++;
  795.     word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  796.  
  797.     nextch = *ptra;
  798.     if (ofs_inbyte != 0) {
  799.         /* shift nextch right by ofs_inbyte bits */
  800.         /* and shift those bits right into word; */
  801.         word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  802.     }
  803.     return (word & masks[nbits]);
  804. } /* rd_dcode() */
  805.  
  806. void init_dtab()
  807. {
  808.     nbits = 9;
  809.     max_code = 512;
  810.     free_code = FIRST_FREE;
  811. }
  812.  
  813. void wr_dchar (ch)
  814. int ch;
  815. {
  816.     if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
  817. #ifdef CHECK_BREAK
  818.     check_break();
  819. #endif
  820.         if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
  821.             prterror ('f', "Write error in lzd:wr_dchar.\n");
  822.         addbfcrc(out_buf_adr, output_offset);     /* update CRC */
  823.         output_offset = 0;                        /* restore empty buffer */
  824.     }
  825.     assert(output_offset < OUTBUFSIZ);
  826.     out_buf_adr[output_offset++] = ch;            /* store character */
  827. } /* wr_dchar() */
  828.  
  829. /* adds a code to table */
  830. void ad_dcode()
  831. {
  832.     assert(nbits >= 9 && nbits <= 13);
  833.     assert(free_code <= MAXMAX+1);
  834.     table[free_code].z_ch = k;                     /* save suffix char */
  835.     table[free_code].next = old_code;            /* save prefix code */
  836.     free_code++;
  837.     assert(nbits >= 9 && nbits <= 13);
  838.     if (free_code >= max_code) {
  839.         if (nbits < MAXBITS) {
  840.             debug((printf("lzd: nbits was %d\n", nbits)))
  841.             nbits++;
  842.             assert(nbits >= 9 && nbits <= 13);
  843.             debug((printf("lzd: nbits now %d\n", nbits)))
  844.             max_code = max_code << 1;            /* double max_code */
  845.             debug((printf("lzd: max_code now %d\n", max_code)))
  846.         }
  847.     }
  848. }
  849. #endif /* ! SLOW_LZD */
  850.